package com.demo.java.OD301_350.OD341;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【猜密码(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146158058
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取输入的数字字符串，按逗号分隔
        String[] numStrings = scanner.nextLine().split(",");
        int n = Integer.parseInt(scanner.nextLine());  // 读取组合的大小

        // 存储所有可能的组合
        List<List<Integer>> combinations = new ArrayList<>();

        // 对输入的数字字符串进行排序，确保数字按升序排列
        Arrays.sort(numStrings);

        // 生成组合
        for (int i = n; i <= numStrings.length; i++) {
            generateCombinations(numStrings, i, 0, new ArrayList<>(), combinations);
        }

        // 如果存在有效的组合，输出
        if (!combinations.isEmpty()) {
            for (List<Integer> combination : combinations) {
                StringBuilder sb = new StringBuilder();
                for (int num : combination) {
                    sb.append(num).append(",");
                }
                // 输出时去掉末尾的逗号
                String combinationString = sb.toString();
                System.out.println(combinationString.substring(0,
                        combinationString.length() - 1));
            }
        } else {
            // 如果没有有效的组合，输出 "None"
            System.out.println("None");
        }
    }

    /**
     * 回溯生成所有的数字组合
     *
     * @param numStrings   数字字符串数组
     * @param k            需要选择的数字个数
     * @param start        当前选择的起始位置
     * @param current      当前的组合
     * @param combinations 所有的有效组合
     */
    private static void generateCombinations(String[] numStrings, int k, int start,
                                             List<Integer> current, List<List<Integer>> combinations) {
        // 如果选择了 k 个数字，添加到结果中
        if (k == 0) {
            combinations.add(new ArrayList<>(current));
            return;
        }

        // 遍历选择数字
        for (int i = start; i <= numStrings.length - k; i++) {
            current.add(Integer.parseInt(numStrings[i]));  // 选择当前数字
            generateCombinations(numStrings, k - 1, i + 1, current, combinations);  // 递归选择下一个数字
            current.remove(current.size() - 1);  // 回溯，撤销选择
        }
    }
}